package newcoder_exp.justPractise;

import org.junit.Test;

public class NC108 {
    public class Solution {
        //淦，这是最大矩形
        public int solve1 (char[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            int[][] left = new int[m][n], up = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    left[i][j] = matrix[i][j] == '1' ? 1 : 0;
                    up[i][j] = left[i][j];
                    if (j > 0 && left[i][j] > 0) left[i][j] += left[i][j - 1];
                    if (i > 0  && up[i][j] > 0) up[i][j] += up[i - 1][j]; 
                }
            } 
            int t, max = 0, idx;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == '1') {
                        t = left[i][j];
                        for (int k = t; k > 0; k--) {
                            idx = i;
                            while (idx >= 0 && left[idx][j] >= k) {
                                idx--;
                            }
                            max = Math.max(max, (i - idx) * k);
                        }
                    }
                }
            }
            return max;
        }   

        public int solve (char[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            int[][] left = new int[m][n], up = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    left[i][j] = matrix[i][j] == '1' ? 1 : 0;
                    up[i][j] = left[i][j];
                    if (j > 0 && left[i][j] > 0) left[i][j] += left[i][j - 1];
                    if (i > 0  && up[i][j] > 0) up[i][j] += up[i - 1][j]; 
                }
            } 
            int t, max = 0, idx;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == '1') {
                        t = left[i][j];
                        for (int k = t; k > 0; k--) {
                            idx = i;
                            while (idx >= 0 && left[idx][j] >= k) {
                                idx--;
                                if (i - idx == k) break;
                            }
                            if (i - idx == k)
                                max = Math.max(max, k * k);
                        }
                    }
                }
            }
            return max;
        }   
    }

    @Test
    public void test() {
        Solution s = new Solution();
        char[][] cs = new char[4][5];
        int[][] nums = new int[4][5];
        nums[0] = new int[]{1,0,1,0,0};
        nums[1] = new int[]{1,0,1,1,1};
        nums[2] = new int[]{1,1,1,1,1};
        nums[3] = new int[]{1,0,0,1,0};
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[0].length; j++) {
                cs[i][j] = (char)(nums[i][j] + '0');
            }
        }
        System.out.println(s.solve(cs));
        /* 
            [[1,0,1,0,0],[1,0,1,1,1],[1,0,1,1,1],[1,0,1,1,1]]
        */
        
    }
}
